home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / unix / zip19p1.zoo / trees.c < prev    next >
C/C++ Source or Header  |  1992-08-18  |  41KB  |  1,085 lines
  1. /*
  2.  
  3.  Copyright (C) 1990-1992 Mark Adler, Richard B. Wales, Jean-loup Gailly,
  4.  Kai Uwe Rommel and Igor Mandrichenko.
  5.  Permission is granted to any individual or institution to use, copy, or
  6.  redistribute this software so long as all of the original files are included
  7.  unmodified, that it is not sold for profit, and that this copyright notice
  8.  is retained.
  9.  
  10. */
  11.  
  12. /*
  13.  *  trees.c by Jean-loup Gailly
  14.  *
  15.  *  This is a new version of im_ctree.c originally written by Richard B. Wales
  16.  *  for the defunct implosion method.
  17.  *
  18.  *  PURPOSE
  19.  *
  20.  *      Encode various sets of source values using variable-length
  21.  *      binary code trees.
  22.  *
  23.  *  DISCUSSION
  24.  *
  25.  *      The PKZIP "deflation" process uses several Huffman trees. The more
  26.  *      common source values are represented by shorter bit sequences.
  27.  *
  28.  *      Each code tree is stored in the ZIP file in a compressed form
  29.  *      which is itself a Huffman encoding of the lengths of
  30.  *      all the code strings (in ascending order by source values).
  31.  *      The actual code strings are reconstructed from the lengths in
  32.  *      the UNZIP process, as described in the "application note"
  33.  *      (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
  34.  *
  35.  *  REFERENCES
  36.  *
  37.  *      Lynch, Thomas J.
  38.  *          Data Compression:  Techniques and Applications, pp. 53-55.
  39.  *          Lifetime Learning Publications, 1985.  ISBN 0-534-03418-7.
  40.  *
  41.  *      Storer, James A.
  42.  *          Data Compression:  Methods and Theory, pp. 49-50.
  43.  *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
  44.  *
  45.  *      Sedgewick, R.
  46.  *          Algorithms, p290.
  47.  *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
  48.  *
  49.  *  INTERFACE
  50.  *
  51.  *      void ct_init (ush *attr, int *method)
  52.  *          Allocate the match buffer, initialize the various tables and save
  53.  *          the location of the internal file attribute (ascii/binary) and
  54.  *          method (DEFLATE/STORE)
  55.  *
  56.  *      void ct_tally (int dist, int lc);
  57.  *          Save the match info and tally the frequency counts.
  58.  *
  59.  *      long flush_block (char *buf, ulg stored_len, int eof)
  60.  *          Determine the best encoding for the current block: dynamic trees,
  61.  *          static trees or store, and output the encoded block to the zip
  62.  *          file. Returns the total compressed length for the file so far.
  63.  *
  64.  */
  65.  
  66. #include <ctype.h>
  67. #include "zip.h"
  68.  
  69. /* ===========================================================================
  70.  * Constants
  71.  */
  72.  
  73. #define MAX_BITS 15
  74. /* All codes must not exceed MAX_BITS bits */
  75.  
  76. #define MAX_BL_BITS 7
  77. /* Bit length codes must not exceed MAX_BL_BITS bits */
  78.  
  79. #define LENGTH_CODES 29
  80. /* number of length codes, not counting the special END_BLOCK code */
  81.  
  82. #define LITERALS  256
  83. /* number of literal bytes 0..255 */
  84.  
  85. #define END_BLOCK 256
  86. /* end of block literal code */
  87.  
  88. #define L_CODES (LITERALS+1+LENGTH_CODES)
  89. /* number of Literal or Length codes, including the END_BLOCK code */
  90.  
  91. #define D_CODES   30
  92. /* number of distance codes */
  93.  
  94. #define BL_CODES  19
  95. /* number of codes used to transfer the bit lengths */
  96.  
  97.  
  98. local int near extra_lbits[LENGTH_CODES] /* extra bits for each length code */
  99.    = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
  100.  
  101. local int near extra_dbits[D_CODES] /* extra bits for each distance code */
  102.    = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
  103.  
  104. local int near extra_blbits[BL_CODES]/* extra bits for each bit length code */
  105.    = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
  106.  
  107. #define STORED_BLOCK 0
  108. #define STATIC_TREES 1
  109. #define DYN_TREES    2
  110. /* The three kinds of block type */
  111.  
  112. #ifndef LIT_BUFSIZE
  113. #  ifdef SMALL_MEM
  114. #    define LIT_BUFSIZE  0x2000
  115. #  else
  116. #  ifdef MEDIUM_MEM
  117. #    define LIT_BUFSIZE  0x4000
  118. #  else
  119. #    define LIT_BUFSIZE  0x8000
  120. #  endif
  121. #  endif
  122. #endif
  123. #define DIST_BUFSIZE  LIT_BUFSIZE
  124. /* Sizes of match buffers for literals/lengths and distances.  There are
  125.  * 4 reasons for limiting LIT_BUFSIZE to 64K:
  126.  *   - frequencies can be kept in 16 bit counters
  127.  *   - if compression is not successful for the first block, all input data is
  128.  *     still in the window so we can still emit a stored block even when input
  129.  *     comes from standard input.  (This can also be done for all blocks if
  130.  *     LIT_BUFSIZE is not greater than 32K.)
  131.  *   - if compression is not successful for a file smaller than 64K, we can
  132.  *     even emit a stored file instead of a stored block (saving 5 bytes).
  133.  *   - creating new Huffman trees less frequently may not provide fast
  134.  *     adaptation to changes in the input data statistics. (Take for
  135.  *     example a binary file with poorly compressible code followed by
  136.  *     a highly compressible string table.) Smaller buffer sizes give
  137.  *     fast adaptation but have of course the overhead of transmitting trees
  138.  *     more frequently.
  139.  *   - I can't count above 4
  140.  * The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save
  141.  * memory at the expense of compression). Some optimizations would be possible
  142.  * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
  143.  */
  144.  
  145. #define REP_3_6      16
  146. /* repeat previous bit length 3-6 times (2 bits of repeat count) */
  147.  
  148. #define REPZ_3_10    17
  149. /* repeat a zero length 3-10 times  (3 bits of repeat count) */
  150.  
  151. #define REPZ_11_138  18
  152. /* repeat a zero length 11-138 times  (7 bits of repeat count) */
  153.  
  154. /* ===========================================================================
  155.  * Local data
  156.  */
  157.  
  158. /* Data structure describing a single value and its code string. */
  159. typedef struct ct_data {
  160.     union {
  161.         ush  freq;       /* frequency count */
  162.         ush  code;       /* bit string */
  163.     } fc;
  164.     union {
  165.         ush  dad;        /* father node in Huffman tree */
  166.         ush  len;        /* length of bit string */
  167.     } dl;
  168. } ct_data;
  169.  
  170. #define Freq fc.freq
  171. #define Code fc.code
  172. #define Dad  dl.dad
  173. #define Len  dl.len
  174.  
  175. #define HEAP_SIZE (2*L_CODES+1)
  176. /* maximum heap size */
  177.  
  178. local ct_data near dyn_ltree[HEAP_SIZE];   /* literal and length tree */
  179. local ct_data near dyn_dtree[2*D_CODES+1]; /* distance tree */
  180.  
  181. local ct_data near static_ltree[L_CODES+2];
  182. /* The static literal tree. Since the bit lengths are imposed, there is no
  183.  * need for the L_CODES extra codes used during heap construction. However
  184.  * The codes 286 and 287 are needed to build a canonical tree (see ct_init
  185.  * below).
  186.  */
  187.  
  188. local ct_data near static_dtree[D_CODES];
  189. /* The static distance tree. (Actually a trivial tree since all codes use
  190.  * 5 bits.)
  191.  */
  192.  
  193. local ct_data near bl_tree[2*BL_CODES+1];
  194. /* Huffman tree for the bit lengths */
  195.  
  196. typedef struct tree_desc {
  197.     ct_data near *dyn_tree;      /* the dynamic tree */
  198.     ct_data near *static_tree;   /* corresponding static tree or NULL */
  199.     int     near *extra_bits;    /* extra bits for each code or NULL */
  200.     int     extra_base;          /* base index for extra_bits */
  201.     int     elems;               /* max number of elements in the tree */
  202.     int     max_length;          /* max bit length for the codes */
  203.     int     max_code;            /* largest code with non zero frequency */
  204. } tree_desc;
  205.  
  206. local tree_desc near l_desc =
  207. {dyn_ltree, static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS, 0};
  208.  
  209. local tree_desc near d_desc =
  210. {dyn_dtree, static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS, 0};
  211.  
  212. local tree_desc near bl_desc =
  213. {bl_tree, NULL,       extra_blbits, 0,         BL_CODES, MAX_BL_BITS, 0};
  214.  
  215.  
  216. local ush near bl_count[MAX_BITS+1];
  217. /* number of codes at each bit length for an optimal tree */
  218.  
  219. local uch near bl_order[BL_CODES]
  220.    = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
  221. /* The lengths of the bit length codes are sent in order of decreasing
  222.  * probability, to avoid transmitting the lengths for unused bit length codes.
  223.  */
  224.  
  225. local int near heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
  226. local int heap_len;               /* number of elements in the heap */
  227. local int heap_max;               /* element of largest frequency */
  228. /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  229.  * The same heap array is used to build all trees.
  230.  */
  231.  
  232. local uch near depth[2*L_CODES+1];
  233. /* Depth of each subtree used as tie breaker for trees of equal frequency */
  234.  
  235. local uch length_co